package 数据结构和算法.剑指offer.动态规划与贪婪算法.剪绳子;

import 工具.打印.PrintUtil;

/**
 * 剪绳子
 * <p>
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
 * 每段绳子的长度记为 k[0],k[1]…k[m-1] 。
 * 请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，
 * 我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18
 * <p>
 * 2 <= n <= 58
 * <p>
 * 剪绳子问题可以转化成为，将一个范围在[2,58]的整数拆分成若干份，使每个部分最后的乘积最大，输出最大的乘积问题。
 * <p>
 * 首先考虑数学方法。由算数几何均值不等式:
 * <p>
 * (n1+n2+...+na)/2≥a√(n1n2...na)   当且仅当n1=n2=...=na时等号成立
 * 因此可以考虑将绳子以相同长度多等分的时候，乘积最大，其次可以猜测绳子以长度3分为多段的时候乘积最大。
 * <p>
 * 算法的思路为当n<=3时，按照规则，至少要分两段，因此返回n-1即可；当n>3时，求出n除3的整数部分a和余数部分b，并分情况讨论：
 * <p>
 * 余数为0，则返回3^a
 * 余数为1，返回3^(a-1)4，因为1+3=2 2=4，但是1 3<2 2，也就是说有一个1就多乘个4
 * 余数为2，返回3^a*2
 */
public class Test {
    public static void main(String[] args) {
        PrintUtil.println(cuttingRope(8));
    }

    public static int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        if (b == 0) {
            return (int) Math.pow(3, a);
        }
        if (b == 1) {
            return (int) Math.pow(3, a - 1) * 4;
        }

        return (int) Math.pow(3, a) * 2;
    }
}
